package lc2;
import java.util.*;
import org.junit.*;
public class Ex93 {
    class Solution {
        List<String> res;
        public List<String> restoreIpAddresses(String s) {
            res = new ArrayList<>();
            char[] cs  = s.toCharArray();
            dfs(cs, 0, 4, new StringBuilder());
            return res;
        }
    
        private void dfs(char[] cs, int idx, int segs, StringBuilder sb) {
            if (segs == 0) {
                if (idx == cs.length) {
                    res.add(sb.substring(0, sb.length() - 1));
                }
                return; 
            }
            int r = cs.length - idx; //还剩下的数位
        
            if (r < segs || r > 3 * segs) {
                return; //剪枝
            }
    
            if (cs[idx] == '0') {
                sb.append('0');
                sb.append('.');
                dfs(cs, idx + 1, segs - 1, sb);
                sb.setLength(sb.length() - 2);
            } else {
                for (int i = 1; i <= 3 && i + idx <= cs.length; i++) {
                    int p = parse(cs, idx, i);
                    if (p < 256) {
                        sb.append(p);
                        sb.append('.');
                        dfs(cs, idx + i, segs - 1, sb);
                        sb.setLength(sb.length() - i - 1);
                    }
                }
            }
        }
    
        private int parse(char[] cs, int i, int len) {
            int res = 0;
            for (int j = 0; j < len; j++) {
                res = res * 10 + (cs[i + j] - '0');
            }
            return res;
        }
    }

    @Test
    public void test() {
        Solution s = new Solution();
        System.out.println(s.restoreIpAddresses("25525511135"));        
    }
}
